МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
ДОСЛІДЖЕННЯ ШВИДКОДІЇ ВИКОНАННЯ МУЛЬТИПЛІКАТИВНИХ ОПЕРАЦІЙ З ДОВГИМИ ЧИСЛАМИ
Лабораторна робота № 2
Варіант № 3
Виконала: студентка групи ІБ-44
Перевірив:
Львів – 2010
Мета роботи: вивчити алгоритми множення та ділення довгих чисел та навчитися розробляти програмне забезпечення для реалізації цих алгоритмів на комп’ютері.
Завдання:
1. Вивчити основні алгоритми множення та ділення довгих чисел, а також способи підвищення швидкодії виконання мультиплікативних операцій з довгими числами.
2. Скласти блок-схеми алгоритмів та програми для реалізації операцій множення (стовпчиком, швидке множення, множення з використанням перетворення Фур’є) або ділення довгих чисел.
3. Дослідити швидкість виконання мультиплікативних операцій для розрядності довгих чисел від 50 до 200. Накреслити графіки відповідних залежностей і порівняти одержані результати.
№
п/п
Варіант представлення числа
Заповнення невикористаних розрядів
Операції з довгими числами
3.
3
використати лічильник
множення довгих чисел з використанням перетворення Фур’є
Список ідентифікаторів констант, змінних і функцій, використаних у головній програмі і підпрограмах та їх пояснення
MaxDig – константа що вказує на максимальну довжину масиву;
оsn – константа що вказує на основу;
Input()- ввід довгого числа з клавіатури;
Output()- вивід довгого числа на екран;
fft() – знаходження ШПФ від числа;
bfft()-знаходження ДПФ від числа;
transf()-здійснює відповідні перенесення;
scal_mult()-здійснює скалярне множення двох векторів;
mult_fft()-множення двох довгих чисел;
ch – елемент типу CHAR;
masCh – масив елементів типу CHAR;
a[] – масив, що представляє довге число;
b[]– масив, що представляє довге число;
c[]– масив, що представляє довге число;
y[][]-двовимірний масив, що представляє довге число;
y1[][]-двовимірний масив, що представляє довге число;
y2[][]-двовимірний масив, що представляє довге число;
i, j, k – цілі змінні, що використовуються в циклі;
malloc()-функція, яка надає змінній динамічну пам’ять;
N, NN, p, k, tt-змінні, що використовуються у підпрограмах.
Програма
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <conio.h>
#include <math.h>
#define MaxDig 100
#define osn 10000
#define Pi 3.141592653589793
void input(long a[MaxDig]);
void output(long a[MaxDig]);
void fft(long a[MaxDig], double y[MaxDig][2], int N);
void mult_fft(long a[MaxDig], long b[MaxDig], long c[MaxDig]);
void scal_mult(double y1[MaxDig][2], double y2[MaxDig][2], double y[MaxDig][2]);
void transf(long c[MaxDig]);
long round(double x);
void bfft(double y[MaxDig][2], long c[MaxDig], int N);
long int*Input( char masCh[])
{
long int *a;
char ch;
a = (long int*)malloc(MaxDig*sizeof(int));
int i = 0;
int j = 0;
for(i = 0; i < MaxDig; i++)
{
a[i] = 0;
}
for(j = 0; masCh[j] != NULL; j++)
{
if ( isdigit(masCh[j]) )
{
for (i = a[0]; i >= 1; i--)
{
a[i + 1] = a[i + 1] + (a[i] * 10) / osn;
a[i] = a[i] * 10 % osn;
}
ch = masCh[j];
int a22 = atoi(&ch);
a[1] = a[i+1] + a22;
if (a[a[0] + 1] > 0)
a[0]++;
}
}
return a;
}
void Output(long int *b)
{
int N = 0;
int NN = 1;
int p;
int b_Osn = b[0];
int i = 0;
for(i = b[0]; i>=1 ; i--)
{
N = b[i];
if (N == 0)
NN = 0;
for (p = 1; N > 0; p = p*10)
{
N = N / 10;
}
while (osn - p != 0)
{
if (b[0] == i)
break;
printf("%c",'0');
p = p*10;
}
if (NN == 1)
{
int result = b[i];
printf("%d",result);
}
NN = 1;
N = 0;
}
}
void fft(long a[MaxDig], double y[MaxDig][2], int N)
{
int i,j,k;
for(i=0;i<MaxDig;i++)
for(j=0;j<2;j++)
y[i][j]=0;
for(j=0;j<N;j++)
{
for(i=0;i<a[0];i++)
{
y[j][0]=y[j][0]+a[a[0]-i]*cos(2*Pi*i*j/N);
y[j][1]=y[j][1]+a[a[0]-i]*sin(2*Pi*i*j/N);
}
}
}
lon...
